public class Test2 {
    //leetcode 718 最长重复子数组
    public int findLength(int[] nums1, int[] nums2) {
        //首先根据经验dp[i][j]表示nums1数组[0,i]之间的子数组和nums2数组[0,j]之间的子数组的最长子数组的长度
        //根据状态定义推导状态转移方程，还是根据最近的状态进行推导，如果nums1[i] == nums2[j]，dp[i][j] = dp[i-1][j-1] + 1
        //但是仔细想一下，发现这样的状态转移方程是不对的，因为dp[i-1][j-1]表示的是nums1数组[0,i]之间的子数组
        //和nums2数组[0,j]之间的最长子数组的长度，但是这个子数组并不能保证是和i，j相连的，所以我们需要更换状态定义
        //dp[i][j]为nums1数组以i位置为结尾和nums2数组以j位置为结尾的子数组中最长子数组的长度
        //通过这个状态表示就可以推导出状态转移方程：
        //当nums1[i] == nums2[j]的时候，dp[i][j] = dp[i-1][j-1] + 1;
        //nums1[i] != nums2[j]的时候，dp[i][j] = 0
        int m = nums1.length, n = nums2.length;
        int[][] dp = new int[m + 1][n + 1];
        //初始化，当num1或者nums2为空数组的时候，不存在相同的子数组
        int ret = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (nums1[i - 1] == nums2[j- 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    ret = Math.max(ret, dp[i][j]);
                }
            }
        }
        return ret;
    }
}
